package com.da.javatest.leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author chenlida
 * @date 2018/12/20 16:30
 * @description
 */
public class Code89 {
    public static void main(String[] args) {
        System.out.println(1 << 1);
        new Code89().grayCode(2);
    }

    //return [i ^ i >> 1  for i in range(2 ** n)]
    //public List<Integer> grayCode(int n) {
    //    List<Integer> list = new ArrayList<>();
    //    for (int i = 2; i < Math.pow(2, n); i++) {
    //        list.add(i ^ (i >> 1));
    //    }
    //    return list;
    //}

    public List<Integer> grayCode(int n) {
        List<Integer> list = new ArrayList<>();
        list.add(0);
        if (n == 0) { return list; }
        list.add(1);
        if (n == 1) { return list; }
        getCode(list, 1, n);
        return list;
    }

    public List<Integer> getCode(List<Integer> r, int start, int end) {
        if (start == end) {
            return r;
        } else {
            int size = r.size();
            for (int i = size - 1; i >= 0; i--) {
                r.add((1 << start) ^ r.get(i));
            }
            return getCode(r, start + 1, end);
        }
    }
}

